package com.yangli.leecode.mashib;

import com.yangli.ahies.study.util.DoubleNode;
import com.yangli.ahies.study.util.ListNode;
import com.yangli.csnote.other.MainOther;
import com.yangli.leecode.mashib.graph.Graph;
import com.yangli.leecode.mashib.interview.*;
import yangli.leecode.mashib.interview.*;
import com.yangli.leecode.mashib.unionSet.UnionSet;

/**
 * TODO
 * https://www.bilibili.com/video/BV1rK411U7VD?p=37&vd_source=ee264bd7d696e9474b767a0b28f15164
 *
 * @Author liyang
 * @Date 2022/11/17 15:19
 */
public class MaxWidthRamp {
    public static void main(String[] args){
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2, l1);
        ListNode l3 = new ListNode(3, l2);
        ListNode l4 = new ListNode(4, l3);
        ListNode l5 = new ListNode(5, l4);
        ListNode l6 = new ListNode(6, l5);
        ListNode l7 = new ListNode(7, l6);
        ListNode res = reverseKGroup(l7, 2);

        System.out.println(res);

        //ListNode res = reverseKGroup(l7, 2);
        System.out.println(res);
    }


    //https://leetcode.cn/problems/maximum-width-ramp/
    public int maxWidthRamp(int[] nums){
        int length = nums.length;
        int j = length - 1;
        int max = 0;
        for (int i = 0; i < length; i++) {
            int start = i + max;
            while (start < j) {
                if (nums[j] >= nums[i]) {
                    max = j - i;
                    break;
                } else {
                    j--;
                }
            }
            j = length - 1;
        }
        return max;

    }

    //单链表反转
    public static ListNode reverseListNode(ListNode head){
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    //双链表反转
    public static DoubleNode reverseDoubleNode(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.pre = next;
            pre = head;
            head = next;
        }
        return pre;
    }


    public static ListNode reverseListNode2(ListNode head){
        return getNext(head);
    }

    public static ListNode getNext(ListNode node){
        if (node.next == null) {
            return node;
        }
        ListNode next = node.next;
        ListNode res = getNext(next);
        node.next = null;//
        next.next = node;
        return res;
    }


    //https://leetcode.cn/problems/reverse-nodes-in-k-group/ 反转K长度链表
    public static ListNode reverseKGroup(ListNode head, int k){
        if (k == 1) {
            return head;
        }
        ListNode start = head;
        ListNode end = getKend(start, k);
        if (end != null) {
            head = end;
        }
        while (end != null) {
            ListNode lastStart = end.next; //下一个循环开始
            ListNode lastEnd = getKend(lastStart, k);//下一个循环结束
            ListNode pre = null;//当前循环结尾，下个循环长度够最后为下个循环尾，否则为头
            if (lastEnd != null) {
                pre = lastEnd;
            } else {
                pre = lastStart;
            }
            ListNode next = null;//反转当前链表
            while (pre != end) {//前一个到达end不再遍历
                next = start.next;
                start.next = pre;
                pre = start;
                start = next;
            }
            start = lastStart;
            end = lastEnd;
        }
        return head;
    }

    public static ListNode getKend(ListNode start, int k){
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }
    /*左神一周刷爆力扣资料
    链接：https://pan.baidu.com/s/1Q35eM01QbbjJaZW2U7Urag
    提取码：bijr

    左神算法代码：https://github.com/algorithmzuo
    代码看下面这个，之后b站更新了代码在里面都能找到*/

    /**新手班**/
    //二维动态规划 二维数组 [i][j] A数组i长度是否匹配B数组J长度
    //A数组无序，B数组对A进行替换，使A有序，最小替换次数
    //1 B数组排序，优先使用小数，最优解
    //
    //if(A[i]>A[i-1]){
    // int[i][j] ans = int [i-1][j]
    // }else{
    // int  temp= j;
    //  while(B[j]<A[i-1]){
    //  temp++
    //  }
    //if(temp>lenght){
    // break;
    // }
    //int[i][j] ans = int[i-1][temp]+1
    // }

    //r、e、d组成字符串，仅有一个长度不小于2的回文串就是好串
    //递归循规查看好串次数
    //当n>4时
    // 好串标准 xx xyx
    // xx 为头时 x为三种，后面一个为两种，在后面的都确定了 6
    // xx 为尾时 x为三种，第一个为两种，后面的都确定了 6
    // xx 为中间 位置有n-3种，x为三种，第一个为两种，其他都确定了 6*（n-3）
    //xyx 为头时 一共6种
    //xyx 为尾时 一共6种
    //xyx 不能为中间
    // 6*(n+1)




    //Math.random() [0,1)随机，精度有限
    //从1-5随机函数 到1-7的随机函数 从a-b随机到c-d随机
    //Math.max(Math.random(),Math.random()) < x 表面 随机两次都落在x范围内的概率即x平方
    //Math.max(Math.random(),Math.max(Math.random(),Math.random())) < x 表面 随机两次都落在x范围内的概率即x立方
    //C. 假如函数f()不等概率返回0和1，那如何等概率返回0，1随机呢？


    //单链表的反转 双链表的反转==>有效的方式就是递归 或者定义临时变量head和pre while循环
    // 链表的k个节点逆序调整


    //位运算求数值位置是否为1  1<<i&num?1

    //n! t = (n-1)!*n res += t 返回t

    //数组返回区间和 1,二维数组，占用空间大，效率高 2，前缀和  l!=0?H[R]-H[L-1]:H[R]

    //选择排序 选择最小的到最前面 冒泡排序 最大的冒泡到最后 插入排序 遍历新增的输插入到前面已排序的位置上
    //归并排序 时间换空间，分割排序，用临时数组合并汇总，n*logn,稳定性好
    //插入排序
    //快速排序 随机选择 三向切分选择 大于小于的临界点 遍历数据 小于则让小于临界点前移并交换 大于则让大于临界点前移并交换 等于则跳过
    //堆排序 数据一个一个给你，从上到下的方法N*logN  数组给你，进行排序。从下到上的方法N 堆最大值返回，然后重新排序，N*logN
    //对数器 简单而低效的方法，用于验证复杂算法正确性

    //条件概率公式 p(a/b) = p(ab)/p(b) 在b事件下出现事件A的概率，等于a、b同时发生概率处于b发生概率

    /*基础班*/
    /*part1*/
    //时间空间复杂度 时间复杂度 O(1) O(logn) O(n) O(n*logn) O(n平方) O(n立方)(线性)  O(2^n) O(3^n) O(k^n)(递归) O(n!)全排列 时间复杂度==>空间复杂度==>常数项
    //对数器 想要测的方法a=> 实现复杂度不好但容易实现的方法b
    //二分法 有序数组查找数组是否存在;有序数据，寻找>=某个数最左的位置;局部最小值 二分法，先判断头尾，选择中间的两便，进行二分    序数组 num位置 二分法  大于num最左的位置 二分法 大于num 保存位置
    //无序相邻不等数组 局部最小 判断头尾，只能较大否则返回，查找中间，如果是局部小返回中间，否则肯定有大于一边，从一边再二分。
    //异或运算 ==>无进位相加 位运算异或 0^a=a a^a = 0 tip:1 实现a,b交换 a= a^b; b=a^b; a=a^b;2数组 某个数奇数次，其他都是偶数，找出这个数 3获取int a最右侧的1=> a&(~x+1)
    //异或运算 ☆ 一个数组，有两种数出现了奇数次，其他数出现了偶数次，找出这两种数==> 异或结果不为0，找出最右侧1进行分组，分组异或出来的结果就是a和b
    /*part2 数据结构*/
    //单双链表反转 删除指定元素
    //栈 双向链表头和尾push尾pop 数组push尾po尾
    //队列 双向链表头和尾push头pop尾 数组 环形数组 putIndex popIndex size limit 解耦前面两个变量 size limit解耦putIndex和PopIndex关联判断
    // 特殊栈返回栈中最小元素，两个栈一个栈正常存放数据，另一个栈存放当前数最小数
    // 栈结构实现队列 两个栈 一个存一个取，取的为空把存的先放到取里面==>队列实现栈 两个队列来回复制
    //递归肯定有一个返回条件;递归都能写成非递归方式;递归利用系统栈 时间复杂度公式（前提是子问题规模等量小）：T（N）=aT(N/b)+O（N^） a:递归方法次数 b分割数据大小 ^:单次递归复杂度 logba <==> d o(N^) 如果相等 n的d次方*logn
    //递归复杂度公式 Master公式  T(N) = a*T(N / b) + O (N^d)  ==>其中 a表示生成的子问题数（比如二叉树的递归遍历就是 a = 2）；b表示每次递归是原来的1/b的规模，O(N^d) 表示除了递归过程之外其他调用的时间复杂度。 若生成的子问题规模不相同，比如T(N) = T(N / 2) + T(N / 3) + O (N^d)，那么便不能用这个公式计算。
    /*    log(b,a) < d	O(N ^ d)
        log(b,a) > d	O(N ^ log(b,a))
        log(b,a) = d	O((N^d) * logN)*/
    //hashMap==>hash表，无序表;O(1)  有序表key有序==>treeMap O(logN)  （AVL自平衡二叉树 SB数  红黑树  跳跃表 空间换时间，建立索引）avl的平衡根据层级，左右层级查不能高于1 sb平衡根据左右节点数量 红黑树通过增加层级误差减少左旋右旋 几个数的差异都是常数级别差异，总的时间复杂度都是logn
    /*part3*/
    //归并排序 时间复杂度n*logn 空间复杂度n。 precess(arr,L,R) mid = (l+r)>>1  precess(arr,L,mid)+precess(arr,mid,r)+merge(arr,l,mid,r) 实质是把比较行为变成了有序信息的传递 n*logn，比n平方要快==>1，最小左数和 细节优化：l+（r-l）>>1 ;2，降序对
    //随机快排 时间复杂度（期望，不稳定）n*logn 空间复杂度logn。less = l-1,more = r,R默认就是基准==>  arr[index]<arr[R] swap(arr,arr[index++],--less)   1,O(N)实现对数组arr根据数字a进行分区。 右边界 小于移动边界并交换，大于跳过 2，三向切分 3，荷兰国旗问题
    //经典快拍 1，随机选择一个数作为基准，并放到最后。2，三色荷兰问题，返回左右边界指针。3，根据左右边界再进行递归 ==>不稳定，选择的数并不能把数组分割成两半，有可能退化为O(N平方)
    /*part4 比较器和堆*/
    // <p>堆</p> <p>队列</p> java的堆就是队列  PriorityQueue 权限队列  数组arr 排序最多移动K距离 k+1 排序小根堆，0位置确定
    //完全二叉树 用数组表示根节点为0 则子节点第一个为 2*i+1 第二位2*i+2 父节点为 （i-1）/2 根节点从1开始 2*i==> i<<1 2*i+1==> i<<1|1 i/2==>i>>1
    //堆 完全二叉树 大根堆 插入数据跟根节点比较交换  heapInsert 移除最大数据，调整二叉树，最小值移到根，子节点最大交换 heapify  heapInsert:新增一个节点排序，从底部向上排序  heapify:删除头节点头，从头开始排序
    //堆排序 数据一个一个给你，从上到下的方法N*logN  数组给你，进行排序。从下到上的方法N 堆最大值返回，然后重新排序，O(N)
    //有一个接近有序的数据，数据移动不超过K个数。如何排序==>N*logK 用有序队列初始前K元素，弹出最小根，加入元素
    //比较器 重载比较运算符==>灵活，泛型编程 => 堆实现resize方法，设置值之后更新堆。要保存数据的位置
    /*part5 排序总结*/
    //前缀树（字典树）  pass 经过 end 结束 nextNode 为空则表示结束  统计这个字符以某个字符出现的次数 这个字符有没有出现 =>增加搜索删除==>实现方式 固定数组或者hash表
    //不基于比较的排序  范围比较窄，桶排序==>计数排序 数字范围比较窄  基数排序 非负且十进制的数字
    //基数排序实现 ==>1，寻找最大位，从个位排序 2，count1数组从左往右统计位数出现的频次 count2数组统计count1统计的前缀3，从右往左遍历原数组，根据位数的在count2的前缀数确定位置。 4依次递归其他位
    //排序稳定性 同样大小的样本再排序之后不会改变相对次序，对于基础类型稳定性毫无意义，对于非基础类型稳定性意义重大
/*
                时间复杂度   空间复杂度     稳定性
    选择排序    O(N^2)      O(1)        无
    冒泡排序    O(N^2)      O(1)        有
    插入排序    O(N^2)      O(1)        有
    归并排序    O(N*logN)   O(N)        有
    快速排序    O(N*logN)   O(logN)     无
    堆排序      O(N*logN)   O(1)     无
    计数排序    O(N)


    O(M)        有
    基数排序    O(N)      O(N)        有*/
    /**part6 <p>链表</p> 面试*/
    //查找链表中点，无额外空间 快慢指针 解决问题方法分类 需要注意元素位置
    //判断链接是否回文 遍历两遍 加入栈 从栈弹出一一比较
    //根据某个值把链接分城 小于等于大于三个区别，sH sT eH eT bH bT变量然后穿起来
    //https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class09/Code04_CopyListWithRandom.java
    //特殊链表结构复制 还有random节点 用hashmap（oldNode，newNode）==>新节点也串在链上，操作完再删除多余引用
    //两个链表相交第一个节点 ==>最简单办法使用hashSet，一一比较相等则为第一个节点。0,找出链表中有闭环的第一个节点 1，无闭环。分别遍历，算出长度差值，长链表先走差值步数，然后一一比较相等则为第一个节点。
    // 2，有闭环两种情况，闭环在环里面和外面
    //约瑟夫环  f(n,m) n表示环中多少人 m表示第几个出局，则f(n.m)最后出局的人在n个人环中，m出局的位置，位置应该再（0，n-1）上。并且有如下规则 f（n，m）= (f(n-1,m)+m)%n
    // 最后的位置肯定为0 int res = 0; for int i =1,i<=n;i++ res = (res+m)%i 从零开始 计算出最终N人时，最后退出的位置
    /**part7 <p>二叉树 </p>  / {@link TreeNode}*/
    //根节点，左右节点；前序头左右 中序左中右 后序左右中遍历 区别就是头节点是先中后开始
    //递归实现序遍历==>非递归利用栈实现序遍历
    //层序遍历 队列实现 每层加入并输出
    //二叉树的序列化==>序遍历，并且序列标记null
    /*part8 二叉树递归 */

    //中序遍历寻找后继节点==>1,如果有右树，找到佑树最左节点。2，如果无佑树，寻找父节点，递归父节点，当父节点是某个节点的左节点是返回父节点。
    //==>在中序遍历寻找前驱或者后继，给定某个节点之后
    //纸条对折==>找到这个二叉树递归规律，初始节点down，down，up，进行中序遍历
    //      二叉树递归讨论 ==>X参与和x不参与
    //二叉树是否是平衡术==>左数右数平衡，且树高差不大于1
    //二叉树的最大距离==> info：树高和最大距离
    //{https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class13/Code02_MaxSubBSTHead.java}
    //二叉树搜索二叉树==> info:最大值最小值最大搜索树节点数是否搜索树
    //员工最大快乐==>info:来最大快乐 不来最大快乐
    /*part9 表和矩阵*/
    //预处理结构和表区别，跟数据参数无关。前缀和就是预处理结构，表对数据参数无关，所有参数出现可能列举了，大表条件就是数据范围较窄。
    //      打表法==>暴力解题找规律
    //小虎苹果问题6n 8n;求24的余数;奇数返回，24前面就几种情况
    //4的倍数，吃草问题==>b  0 后 1 先 2 后 3先4 先==>n%5==0/2为后手
    //连续正数之和 ==>暴力解推到规律==>num&(num-1)==0表示num是2的某次方==>大于3时，2的n次方为false
    //数组开关问题
    //      矩阵处理技巧==>宏观规划
    //z打印矩阵==>A B斜线 运动轨迹，A先横向移动在竖向移动 B相反
    //转圈打印矩阵
    //正方形矩阵旋转==>按照矩阵分成圈 即使a b c d一圈，分成n-1组进行交换
    /*part9 并查集结构和图相关算法*/
    //      贪心算法解决===>尝试以局部最优达到结果最优==>以生活经验为主，面试题目不好判断
    //会议安排最优解==>暴力解法:每次用剩余会议，已经安排数据，会议截止时间进行递归==>贪心算法：最优解 结束时间越早的有限安排，每次排会议也是先判断某个会议时间是否大于上个会议截止时间
    //暴力解一般都是递归，前一种的情况往后面递归，还要注意递归的时候回来的时候需要恢复现场
    //X.放灯的问题 给定一个字符串str，只由‘X’和‘.’两种字符构成。 ‘X’表示墙，不能放灯，也不需要点亮 ‘.’表示居民点，可以放灯，需要点亮 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮 返回如果点亮str中所有需要点亮的位置，至少需要几盏
    /**
    {@link GoldCut}
    //切金条==>暴力解法 遍历数据，从i=0开始切，向下递归，传参是剩余未分割大小和消耗金币，返回最小金币
    //贪心算法之利润最大问题==>先把项目根据投入加入小根堆，弹出符合初始资金的项目，加入以利润为基础的大根堆，选择利润最大根，循环K次，初始资金加上最大利润
    //https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class14/Code05_UnionFind.java
    //<p>并查集</p> {@link UnionSet} ==> hashMap 存储值到对象映射 一个节点到另一个几点，当前节点父节点映射 根节点子节点数量 isSame  union==>findFather==>小集合挂大集合 方法常数级别调用
    //用户三个属性 合并用户==>三个属性三个map，新增用户如果查找到用户，合并查找的用户和新用户

    //<p>图</p>{@link Graph}   点集 边集 有向图 无向图==>双向有向图==>图的表示，邻接表示法 矩阵表示法（全连接）==>通过统一的转化，把图转化成统一对象 node value in out nexts edges
    //bfs 宽度（广度）优先遍历，距离我进的先遍历==>队列+set 队列 控制当前节点和下一个节点 set控制那些已经注册过了，防止循环 队列弹出元素使用元素
    //dfs 深度优先遍历，一条路走到底==>栈+set（控制循环） 栈加入元素使用元素
    //图的拓扑排序 前提 有向图且无环 一个节点依赖前一个节点或者多个节点==>优先寻找入度为0的节点，并消除节点作为其他节点入度，找下一个 准备一个map存放节点和他的入度数 遍历入度为0的集合
    //https://github.com/algorithmzuo/algorithmbasic2020/tree/master/src/class16
    //最小生成树 kruskal==> 所有边集排序遍历+并查集进行合并点
    //最小生成树 P算法==>某个点出发,点加入set，解锁边加入小根堆，选取最小边添加到结果集，如果有新点加入set，解锁新点新解锁的边到小根堆。从小根堆选择最小，出发如此以往。相当于每次选择边加入了新的点，一个点一个点加不需要并查集，如果不是新的点就不要了
    //Dijkstra dj算法 边为正数即每次路径都有加权 求最短路径==>TSP 图是全连接，从出发点回到出发点，其他点只能一次，距离一次
    //a起点  到所有点的最短距离表 小根堆==>自定义实现堆
    part11 暴力递归
     大问题拆除同类问题的小问题，到basecase，得子问题后的决策，返回需要的解而不是每一个问题解==>不记录每个问题的解是暴力递归，记录每个问题的解是动态规划
     1.从左往右的尝试模型
     汉诺塔问题==>n从左到右分为三步 第一步，n-1从左到中 第二步 第n个移动到右 第三不 n-1从中移动到右 ==>2*f(n-1) +1==> 2^n-1+2^n-2+....1==>2^N-1
     反转栈且不适用额外空间==>
     打印所有子序列（递归四个参数1，原始字符数组 2，递归到数组索引 3，当数组递归完收集字符串的集合 4，前面递归路径 ）==>子串连续顺讯的元素 子序列可以不连续，但是顺序不能乱（比子串要多）
     打印所有子序列，不出现重复字面值的子序列==>收集的时候用set去重就可以了
     打印字符全排列，去重==>分支限界
     从左往右的尝试模型1
     数字转换，1对A，2对B，数字字符串转化结果数量{@link Recursion}  【题目转化成 动态规划】
     从左往右的尝试模型2
     经典背包 两个数组表示重量和价值，如何在重量限制下最大价值{@link Recursion} choose方法
     以背包问题为例 暴力搜索复杂度 2^n ==>记忆化搜索 n*bag==> 有限的状态或者枚举(=经典动态规划) >=  经典动态规划
     2.范围上尝试的模型
     一个数组，只能从最左或者最有拿牌，AB都是非常聪明并且依次拿牌，求获胜者最大分数 {@link Recursion} win方法 【题目转化成 动态规划】
     人过河鳄鱼问题==>鳄鱼为奇数不能过河，鳄鱼为偶数可以过河。 五个海盗分100金币==>逆序倒退 1号利益最大化的方案：98、0、1、0、1（3:2）；这个方案50%会死亡。 1号最保险的方案：97、0、1、0、2（3:2）；该方案保证活命。
    欧拉信封==>n个信封两种情况1，A给到某人B，B又寄给A 则可能为 f(n)=（n-1）*f(n-2) 2,A给到某人B，B不寄给A，可以把AB看成一个节点，有一个入度一个初度 f(n)=（n-1）*f(n-1)   总的表达式 f(n)=(n-1)(f(n-1)+f(n-2))
     N皇后问题 {@link Recursion} queen方法==>优化的方式 位运算 加速常数时间
     part11 动态规划 ==>暴力递归过程中有重复计算，保存起来减少计算==>记忆化搜索==>有几个可变参数就是几维表
     不是所有暴力递归能够转化成动态规划的，所有的动态规划都是来自暴力递归==>没有足够多的重复的过程
     斐波那契数列，又称黄金分割数列 f(n)=f(n-1)+f(n-2)==>一个可变参数
     N个点 在M位置 走K步 到P点 {@link DynamicProgramming}==>dynamic programming==>两个可变参数

     重点题目【1】数组元素，为正且不重复，可以重复使用求等于目标target的方法==>{@link DynamicProgramming} moneyTarget
     重点题目【2】 贴纸拆分
     面试中设计暴力递归的原则
     1，每一个可变参数，一定不要比int类型更复杂（对象或者数组就不合适） 2，如果违背1，让类型突破到一维线性结构，必须是唯一参数 3，如果是2，只需要做到记忆化搜索 4 可变参数越少越好

     动态规划的进一步优化 空间压缩 状态化简  四边形不等式

     3，多样本位置全对应的尝试模型
     4，寻找业务限制的尝试模型


     最大长度公共子序列 ==>双数组动态规划，i长度和j长度串最大公共子序列 dp[i][j] = max(dp[i][j-1],dp[i-1][j])
                                                            if(s1[i] = s2[j]) dp[i][j] = max(dp[i][j],dp[i-1]dp[j-1]+1)
     最长回文子串==>马拉车算法

     数据量猜测解法==>c运行1s，java运行2s，能处理数据量大概是10^8,不能超过10^8的数据量==>如果数据量是10^6或者10^7左右解法肯定是O(N)或者O(N*logN);如果数据量是10^3解法可以是O(N^2)


     //https://www.bilibili.com/video/BV1rK411U7VD/?p=57
     面试刷题
     1绳子覆盖最多的点数 a:以index为结尾，查找减去长度的范围内的个数 n*logn  ==> 最优解b:滑动窗口
     2让一种字符放左，一种字符放右，最少要交换几次。比较两种情况，某个字符全部放左或者放右。放左的时候，初始i=0，找到对应字符的index,得到这个字符移动记录index-i;i++,index继续遍历。累加改字符所有移动记录
     3 以+-连接数字，返回得到目标target的方法。{@link Interview}  https://leetcode.cn/problems/target-sum/  https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class01/Code07_TargetSum.java
     4,偶数司机，分配到AB区域，每个司机每个区域收益不同，求收益最大。 {@link Four} https://www.bilibili.com/video/BV1rK411U7VD?p=59&vd_source=ee264bd7d696e9474b767a0b28f15164
     5-60,如何实现hashmap setAll方法，并且复杂度为O(1)==>新增三个变量 int all;long time map最后一次更新时间；alltime setall最后一次更新时间默认long最小值。put(key,{value,time}) get的时候，先判断time>alltime?value:all
     6-61 最长无重复子串长度 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
     7-62 数组小于k的范围 {@link Seven}==>等于k：先排序，进行贪心，左右指针，值大于k，R移动否则l移动。要标记已经使用的位置，
     8-63 数组表示多人体重，船的限制limit，最多两人，船最少。前面优化就是大于limt的抛弃。从中间开始，LR遍历，L上满足limitR的个数，L移动R个。最后结果满足个数/2+不满足/2（向上取整）+未标记的一个
     9-64 数组中子数组累加和最大==>遍历 ans保存过程中最大数值，前缀累加和变大{@link Nine}
     10-65 分糖果 最少一个 大于要多小于要少 等于不变   从左到右left查找左坡 从右到左right查找右坡 比较两个数组最大值   https://leetcode.cn/problems/candy/
     11-66 字符串交错问题    dp[i][j] = （s1[i-1]=s[i+j-1] &&dp[i-1][j]）||（s1[j-1]=s[i+j-1] &&dp[i][j-1]）  https://leetcode.cn/problems/interleaving-string/
     12-67 树结构相等 递归调用==>g(left)+g(right)+same(left,right)?1:0==>a==null^b==null 一个为空一个不为空
     13-68 编辑距离==>两个字符串相似程度  dp[i][j] =  Math.min(dp[i-1][j]+d,dp[i][j-1]+a,dp[i-1][j-1]+s[i-1]==s[j-1]?0:r) leecode72题
     14-69 计算字符串公式结果==>化学式元素个数、压缩串==f(n) = info(ans,end){@link Fourteen}
     15-70 最大水量==》双指针
     16-71 简单题目：有效的括号==>用栈，左括号压栈，右括号弹出  升级题F目：无效括号串变成有效的所有可能
     17-72 最长递增子序列长度 {@link Seventeen}
     18-73 定义一个数的stepnum的规则，查找有没有数到stepNum{@link Eighteen}
     19-74 跳跃游戏次数最少 数组上的点表示能跳几步，到最后最少的跳跃次数--jump-game {@link Nineteen}
     20-75 布尔表达式的期待方法数
     21-76 N张牌 小于a继续抽 大于等于a 小于b赢 大于等于b输求赢的概率==>f(n) = (f(n+1)+f(n+1)*N-f(n+1+N))/N {@link TwentyOne}
     22-77 超级洗衣机问题==>接雨水问题 {@link TwentyTwo}
     23-78 约瑟夫环问题==>Y=x%i变形来的，移动函数规律左加右减，上加下减==>后面的编号推到前面编号 f(n,m) 表示n节点m移除，剩余的节点编号 = (f(n-1,m)+m-1)%i+1 basecase n=1 return1==>也可以转成for循环 {@link MainOther}LastRemaining_Solution
            //base case n=1 return 0==>f(n,m)=(f(n-1,m)+m)%n 后面的编号推到前面的编号
     24-79 每一行有序 每一列有序的二维数组，给定正整数k，求数组中最小的第k个数. 1，在数组中查找小于n的数有多少个，并且返回最接近实际的数m。2，从数组最大值和最小值之间开始二分查找，用mid进行1返回小于mid的个数和接近数，如果mid.num小于k，则 l = mid继续递归，直到mid。num==k，返回最接近的数。==>java的有序表treeSet
     25-80 S字符串有多少个子序列等于T字符串 样本对应模型   d[i][j]s拿前i个字符，有多少子序列等于T的前j个字符的前缀串  dp[i][j]=dp[i-1][j]+S[i]==T[j]?dp[i-1][j-1] basecase dp[0][j]=0 dp[i][0]=1==>单行或者单列都能够进行空间压缩
     26-81 给定一个str,返回str有多少种不同的字面值的子序列  leecode distinct-subsequent-li
            无重复情况 n = 2^n ==> 有重复 f(n) = 2*f(n-1)-f(n-1)'  f(n-1)'表示这个重复字符上一次位置上的记录数的   前+(前+“1”)==>前‘+(前’+“1”) 前‘包含了(前+“1”)和前’+“1”重复,需要减去(前+“1”)数据，也就是前的数据。上次出现数值前一个的数量
            数值太大取模运算 1，(f(n-1)+f(n-1))%m = A f(n-1)'=B 2  2f(n) = (A-B+m)%m ==>A-B可能为负数
     27-82 联通两块岛的最短路径  https://leetcode.cn/problems/shortest-bridge/comments/ {@link TwentySeven}
     28-83 LRU内存算法 hashMap+双向链表
     29-84 最小包含区间问题==>多行有序，使的答案的区间最小并且包含所有行至少一个数==>取出每行最小值放入有序表，排序后记录当前区间，表示从某个最小值开始的最小区间，弹出最小值，并在最小值所在的行取第二个，继续表示当前以某个最小值为开始的最小区间，比较两个区间取最小。遍历当数组越界返回，表示某行的某个值为最小值的可能已经遍历完。
          堆==>大/小根堆 ==>PriorityQueue  有序表快速能够查找到表中的最大值最小值==>链表或者数组实现，数据有序  java的有序表就是treeSet
     30-85 一维接雨水问题 {@link TwentyTwo} ==>最优解不需要辅助数组，用左右指针，记录左右当前最大值，那个值相对小取计算那一边
     31-86 二维接雨水问题 创建一个对象包含值和坐标信息。先把最外一圈的表示成对象放到小根堆里面，取出最小值，为max表示当前一圈或者湖的瓶颈。开始向上下左右未去过的地方传染（还有申请一个辅助数据记录进入过堆的位置，进入堆计算水量，当前值减去max。如果大于max水为0，按顺序弹出，弹出的值大于max更新max。从弹出的地方传染。
     32-87 超级水王问题（摩尔投票） 数组中某个数出现频次大于一半，int num，count num==0表示无候选，下个数默认候选，count候选者频次，不同值--同++。最后统计num的次数大于一半==>出现频次大于n/K的数 定义k-1的数组
     33-88 合并石头的最低成本 https://leetcode.cn/problems/minimum-cost-to-merge-stones/solution/yi-dong-you-yi-dao-nan-yi-bu-bu-shuo-ming-si-lu-he/ {@link ThirtyThree}
     34-89 最小包含子串 单调性左右指针，L从0开始，到R++找到符合条件字符串，统计长度然后L--直到不满足字符串，然后再R++
     https://leetcode.cn/problems/M1oyTv/solution/han-you-suo-you-zi-fu-de-zui-duan-zi-fu-a8q50/
     35-90 每种字符串只保留一个，尽量按照字典顺序保留。贪心策略：移除重复字符使的按照字段排序，查找到符合条件的子串，子串从L遍历到某个字符为0位置R，L..R中选择最右侧的字典顺序字母a，从L=a位置，重复操作选择b
     https://leetcode.cn/problems/remove-duplicate-letters/ {@link ThirtyThree}
     36-91 三个有序数组选三个数相减绝对值最小==>最窄区间，2*最窄间隔==>29-84 最小包含区间问题
     37-92 鹅厂文化衫问题，对文化衫颜色进行调查，返回数组，数字表示当前人说跟我一样颜色人还有几个，（除了自己），每个人回答准确,不过有可能有的答案没有采集，求最小可能的人数 minPeople {@link ThirtySeven}
            例如返回1有三个，最小可能是第一第二1成一对，第三单独一对，第四个未收集答案。则人数为4个。通用公式C的X个，C/X+1*（x+1）  其中向上取整*a/b向上取整==(a+(b-1))/b==>(c+x)/(x+1)*(x+1)
     38-93 有效的括号（leetcode 0020）栈的压入和弹出 遇到左加入，遇到右比较弹出==>常数项的优化 如何自己实现简单的栈 定义一个数组 char [] str = new char[N];int size; 1.push方法 str[size++] = '1';2.pop方法 str[size--] 记得str[size] = null漏洞 3，size==0判断为空
     39-94 有效的数独 leetcode 0036
     40-95 数独的解 leetcode 0037 {@link Forty}
     41-96 小数的次方 pow leetcode0050==>经典二分：基础整除的n次方 75二进制 1001011 10^75 = 1*10^1*10^2*10^8*10^64{@link FortyOne}
     42-97 根号  0069  也是二分法 {@link FortyOne}
     43-98 矩阵置零 0073 使用行列两个数组维护为0的行列，遍历一遍就行了 如何省空间==>定义两个变量rowZero和cloZero表示0行0列是否变0，然后用0行0列记录ij为零的位置，相当于辅助数组==>用一个变量{@link FortyThree}
     44-99 乘积最大连续子数组 0152 {@link FortyFour}
     https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class32/Problem_0152_MaximumProductSubarray.java https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class32/%E8%AF%B4%E6%98%8E
     45-100 172 阶乘后的零,数字零的由来是2*5，一般阶乘5的因子少，计算5的因子就可以算出0的个数。每5个数出现一个5的因子，每25个数又会多出现以恶5的因子，每125个数又会多出现一个5的因子。ans = n/5+n/25+n/125...知道 n除以5的阶乘为0
     46-101 190 数字二进位颠倒后的数字，进行位运算，不能转成字符串。对32位int，进行依此转换前2^n位。 n>>>16||n<<16==> (n&0xff00ff00)>>>8||(n&0x00ff00ff)<<8==>(n&0xf0f0f0f0)>>>4||(n&0x0f0f0f0f)<<4==>(n&0xcccccccc)>>>2||(n&0x3333333)<<2==>(n&0xaaaaaaaaaa)>>>1||(n&0x555555555)<<1
     47-102 0204 1-n的素数个数 {@link FortySeven} 1.枚举n种的每个数，然后除以2--根号n的数，看看能够除尽。为啥是根号N，如果一个数能被除尽最小的因子就是根号N 2埃氏筛 3线性筛选
     48-103 额外题目 出卷子，一个数组表示卷子难度，现在给你一个数M，表示前一个题目难度比当前难度大于M {@link FortyEight}==>indexTree add(index,v) sum(index)前缀和 线段树 节点用数组存储区间
     49-104 0213 打家劫舍i 求数组种不连续子序列最大 憋转移方程 count ==>II 数组是环形 count2{@link FortyNine}
     50-105 0277 查寻名人==>1，遍历查找出可能是候选人的节点，别人知道我，我不知道别人,2从我的左边验证我不认识别人 3，从头开始验证，别人认识我
     51-106 0279 完全平方数,一个数可以被拆成几个平方数==>四平方和定理，任何自然数的最小平方和数量不超过4 {@link Fifty#numSquares}
     52-107 0289 生命游戏==>利用位信息保存下一步变化的信息 {@link Fifty#gameOfLife}
     53-108 0326 是否是3的幂 ==>非常取巧，利用1162261467取模，能为0表示为3的幂 {@link Fifty#isPowerOfThree}
     54-109 0340 至多包含k个不同子串的最大长度==>单调性，窗口范围和种类是正相关，滑动窗口 左右指针 {@link Fifty#lengthOfLongestSubStringKDistinct}
     55-110 0380 O(1)删除和随机获取元素 ==>用两个map一个记录值和索引映射，一个记录索引和值的映射，这样就可以查询和删除都是O(1)了，删除时候默认把最后的索引位置值更新到删除位置上，这样就可以随机获取了
     56-111 字符串str在新字典序中是第几个==> {@link Fifty#kth}
     57-112 魔法石头过河 贪心==>类似4,偶数司机问题
     58-113 把一个01字符串切成多个部分，要求每一部分呢01的比例一样，同时要求尽可能多的划分,前缀n可以划分部分数{@link FiftyEight#function==>0...n的比例a:b,中包含a:b的数量为n，结果为n+1。 1,如何求最大公约数  2,不同的斜率如何保存==>Map<Integer,Map<Integer,Integer>>
     59-114 给定一个数组arr,当拿走某个数a时候，其他所有书+a，求最终拿走所有数的最大分数==>贪心算法，先拿走大的分数，最小的分数不想加，排序拿
     60-115 给定一个str，和一个正整数k，返回长度为k的子序列中，字典序最大的子序列==>单调栈，实际上是一种贪心，前面最优不会受后续影响 {@link FiftyEight#kthMax
     61-116 由0和1组成的字符串，1开始价值为1，大于1时，和前一个相等价值加1，和前一个不相等价值为1，可以删除任务字符价值最大。{@link FiftyEight#maxValue
     62-117 由01234组成字符串，1左边的0可以一起消除01,3左边的2可以一起消除23，给定字符串可以完全消除的最长子序列是多少。{@link SixtyTwo#maxSubStr
     63-118 一个无需数组长度为n，所有数组都不一样，并且值都在0..n-1上，返回让数组变成有序的最小交换次数==>1,离散化让一组数字变成，0.。。n-1的数组，copy数组进行排序，map中存放数字和位置映射，原数组替换数组的位置信息。 2,0.。n-1上如何快速交换变成有序，{@link SixtyTwo#minSort leecod二原题
     64-119 leecode31 一个数组的全排列按照字典序，给定其中一个排列，求下一个排列==>从右往左遍历找到第一个下降的位置，再次遍历找到比下降为止刚好的大的数，进行交换，下降为止之后的数进行逆序。 {@link SixtyTwo#nextPermutation
     65-120 leecode0296 最佳聚合地点 ==>最佳的位置肯定是在最优的行和最优的列的位置上，最优的行只指各行的1移动到某一行总成本最低==>可以比较两行那个不是最优解{@link SixtyTwo#minTotalDistance
     66-121 执行x和y操作让累加和小于等于0的最小代价,给定正整数数组，不变代价为0，变0代价为x，取反代价为y，求数组和小于等于0的最小代价，xy>0.{@link SixtySix#minValue}
     67-122 leecode992 一个数组中，子数组中不同正数的个数为k，求子数组个数。方法一，滑动窗口，用一个map记录大小和数字频次，size==k时++，小于k r++,大于k，l--。{@link SixtySeven#subarraysWithKDistinct}
     68-123 利用魔法积木来做到合并最大。1，上面的积木不能小于下面的积木 2，上面的积木减去下面的积木不能超过X 3最下面的积分没有要求 有一个数组表示积木，和能表示任意数的魔法积木K，求最小的堆数。
            两个贪心 1，数组排序，相邻的尽量的在一起，减少间距。2，差值超过X的形成数组也排个序，优先处理最小的。 {@link SixtySeven#minSplit}
     69-124 leetcode 0475 供暖器 数组排序==>找到每一个地点的最小的差值，选择最大差值{@link Seventy#min}
     70-125 一个数组，所有的可能差值，第k小。找到所有数组绝对值第k小 {@link Seventy#kthAbs}
     71-126 迷宫iii 499宽度优先遍历
     72-127 446  等差数列的数量 {@link Seventy#numberOfAS}
     73-128 489 机器人扫地最优方式 {@link Seventy#cleanRoom}
     74-129 875 爱吃香蕉的可可{@link Seventy#minEatingSpeed}
     75-130 1035 不相交的线==>最大长度公共子序列 动态规划 dp[i][j] = max{dp[i-1][j],dp[i][j-1]} if(dp[i]==dp[j])dp[i][j] = max(dp[i][j],dp[i-1]dp[j-1]+1)
     76-131 683 K个关闭的灯泡 bulbs==>在第i+1小时开启第value个灯泡==>days 第i个灯泡在第几个小时亮 {@link SeventySix#kEmptySlot}
     77-132 1488 避免洪水泛滥 {@link SeventySix#kEmptySlot}
     **/
}

